package com.jjlin.chapter_3;

import java.util.*;
public class CD169{
    //二叉树节点
    public static class Node{
        public int val;
        public Node left;
        public Node right;
        public Node(int data){
            this.val = data;
        }
    }

    //建立二叉树
    public static Node createNodeList(int[][] nums, int root){
        if(nums == null || nums.length == 0 || nums[0] == null || nums[0].length == 0)
            return null;
        HashMap<Integer, Node> map = new HashMap<>();
        for(int i = 0; i < nums.length; ++i){
            map.putIfAbsent(nums[i][0], new Node(nums[i][0]));
            if(nums[i][1] != 0){
                map.putIfAbsent(nums[i][1], new Node(nums[i][1]));
                map.get(nums[i][0]).left = map.get(nums[i][1]);
            }
            if(nums[i][2] != 0){
                map.putIfAbsent(nums[i][2], new Node(nums[i][2]));
                map.get(nums[i][0]).right = map.get(nums[i][2]);
            }
        }
        return map.get(root);
    }

    //找出二叉搜索树的两个错误节点
    //方法：
    // 1、有两处降序，则错误节点为前一个降序的第一个节点和后一个降序的第二个节点，比如中序遍历为1 5 3 4 2,则错误节点为5和2，互换即可
    // 2、有一处降序，则错误节点为这个降序的第一个和第二个节点，比如中序遍历为1 2 3 5 4,则错误节点为5和4
    public static Node[] getTwoErrNode(Node head){
        Node[] res = new Node[2];
        if(head == null)
            return res;
        Stack<Node> stack = new Stack<>();
        Node cur = head;
        Node pre = null;
        while(!stack.isEmpty() || cur != null){//进行后序遍历
            if(cur != null){
                stack.push(cur);
                cur = cur.left;
            }else{
                cur = stack.pop();
                if(pre != null && pre.val > cur.val){
                    res[0] = res[0] == null ? pre : res[0];
                    res[1] = cur;
                }
                pre = cur;
                cur = cur.right;
            }
        }
        return res;
    }

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int root = sc.nextInt();
        int[][] nums = new int[n][3];
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < 3; ++j)
                nums[i][j] = sc.nextInt();
        Node head = createNodeList(nums, root);
        Node[] errNodes = getTwoErrNode(head);
        if(errNodes[0] != null && errNodes[1] != null)
            System.out.print(errNodes[0].val < errNodes[1].val ? (errNodes[0].val + " " + errNodes[1].val) : (errNodes[1].val + " " + errNodes[0].val));
    }
}
